package week_08;

import java.util.*;

public class Dijkstra_850 {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int m = input.nextInt();

        // 使用出边数组处理数据
        List<List<Integer>> ver = new ArrayList<>();// 记录出边点
        List<List<Integer>> edge = new ArrayList<>();// 记录边权
        boolean[] isVisit = new boolean[n + 1];
        int[] dist = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            ver.add(new ArrayList<>());
            edge.add(new ArrayList<>());
            dist[i] = (int) 1e9;
        }

        // 读取入边
        for (int i = 1; i <= m; i++) {
            int x = input.nextInt();
            int y = input.nextInt();
            int z = input.nextInt();
            ver.get(x).add(y);
            edge.get(x).add(z);
        }
        // 没有被处理过的dist最小的优先队列
        PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> {
            return o1[1] - o2[1];
        });

        dist[1] = 0;
        queue.add(new int[]{1, 0});
        while (!queue.isEmpty()) {
            int[] top = queue.poll();
            int x = top[0];
            if (isVisit[x]) continue;
            isVisit[x] = true;
            for (int i = 0; i < ver.get(x).size(); i++) {
                int y = ver.get(x).get(i);
                int z = edge.get(x).get(i);
                if (dist[y] > dist[x] + z) {
                    dist[y] = dist[x] + z;
                    queue.offer(new int[]{y, dist[y]});
                }
            }
        }

        int ans = dist[n] == (int) 1e9 ? -1 : dist[n];
        System.out.println(ans);
    }
}
